import time
import random

class Sorter(object):
    def __init__(self, l:list):
        self.__temp = [0 for _ in range(0, len(l))] 
        self.__list = l

    def sort(self):
        self.sort_list(self.__list, 0, len(self.__list) - 1)

    def sort_list(self, l, start, end):
        if end <= start:
            return
        mid = start + (end - start) // 2
        self.sort_list(l, start, mid)
        self.sort_list(l, mid + 1, end)
        self.merge(l, start, mid, end)

    def merge(self, l, start, mid, end):
        for i in range(start, end + 1):
            self.__temp[i] = l[i]

        j = start
        k = mid + 1

        for i in range(start, end + 1):
            if j > mid:
                l[i] = self.__temp[k]
                k += 1
            elif k > end:
                l[i] = self.__temp[j]
                j += 1
            else:
                if self.__temp[j] < self.__temp[k]:
                    l[i] = self.__temp[j]
                    j += 1
                else:
                    l[i] = self.__temp[k]
                    k += 1
                
if __name__ == "__main__":

    l = [random.randint(0,50000) for _ in range(50000)]
    #l = [3,2,5,7,3,9,1]
    sorter = Sorter(l)

    before = time.time()
    sorter.sort()
    after = time.time()
    print(after - before)  